package queue.homework;

import java.util.LinkedList;
import java.util.Queue;

/**
 * 思考：上面的方式，push是O(1)的，pop是O(n)的。能不能写一个实现push是O(n)的，pop是O(1)的
 *
 */
public class MyStack3 {
    private Queue<Integer> q;


    /**
     * Initialize your data structure here.
     * O（1）
     */
    public MyStack3() {
        q = new LinkedList<>();
    }

    /**
     * 对于一个栈来说，关键是栈顶在哪里。
     * <p>
     * 栈是一端入，同一端出；而队列是一段入，另一端出。如果只给一个队列，我们先假设，出队的一端是栈顶。
     * <p>
     * 一旦这样定义，那么，我们封装的这个MyStack的出栈操作就很简单：直接把元素出队即可
     * <p>
     * 定义队首为栈顶，出栈等同于出队，入栈就需要借助另外一个队列，先将要入栈的元素在新队列入队，然后将旧队列中的元素全部出队然后在新队列中入队
     * <p>
     * O（n）
     *
     * @param x
     */
    public void push(int x) {
        Queue<Integer> q2 = new LinkedList<>();
        q2.add(x);
        while (q.size() > 0) {
            q2.add(q.remove());
        }
        q = q2;
    }


    /**
     * 而我们的top过程，因为拿出栈顶元素后，top里存放新的栈顶元素，所以，我们也需要维护top，注意下面的注释：
     *
     * @return
     */
    public int pop() {
        return q.remove();
    }

    /**
     * 这样以来，top函数就变得非常简单了
     * O(1)
     *
     * @return
     */
    public int top() {
        return q.peek();
    }

    /**
     * O(1)
     *
     * @return
     */
    public boolean empty() {
        return q.isEmpty();
    }

    /**
     * O（1）
     *
     * @return
     */
    public int getSize() {
        return q.size();
    }
}
